import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Algorithm2{
 	static void Random(NewState2 state){
 		List<Planet> myPlanets = state.MyPlanets();
 		List<Planet> notMyPlanets = state.NotMyPlanets();
		Random random = new Random();
		int source = myPlanets.get(random.nextInt(myPlanets.size())).PlanetID();
		int dest = notMyPlanets.get(random.nextInt(notMyPlanets.size())).PlanetID();
		
		state.IssueOrder(source, dest);
	}

	static void BFBot1(NewState2 state, int heuristicNumber){
		int searchDepth = 3;
		List<List<NewState2>> stateTree = new ArrayList<List<NewState2>>();
		List<NewState2> levelOneFloor = new ArrayList<NewState2>();
		levelOneFloor.add(state);

		stateTree.add(levelOneFloor);

		int bestHeuristic = Integer.MIN_VALUE;
		NewState2 bestState = null;

		for (int i = 0; i < searchDepth; i++)
		{
			List<NewState2> currentFloor = stateTree.get(i);
			List<NewState2> nextFloor = new ArrayList<NewState2>();
			boolean endStateFound = false;
			for (NewState2 NewState2 : currentFloor)
			{
				// Hier voor de huidige state alle mogelijke volgende States toevoegen aan nextFloor
				for (Planet myPlanet : NewState2.MyPlanets())
				{ 
					//*Tikkeltje Efficienter denk ik
					for(Planet planet : NewState2.NotMyPlanets()){
						NewState2 stateToAdd = NewState2.clone();
						stateToAdd.setParent(NewState2);
						// Voer actie uit myPlanet valt neutralPlanet aan
						stateToAdd.SendFleet(myPlanet, planet);

						nextFloor.add(stateToAdd);
						int heuristic = stateToAdd.getScore(heuristicNumber);
						if (heuristic == Integer.MAX_VALUE)
						{
							// Eindstaat gevonden, stoppen met zoeken
							endStateFound = true;
							break;
						}
						else if (heuristic > bestHeuristic)
						{
							bestHeuristic = heuristic;
							bestState = stateToAdd;
						}
					}
					if (endStateFound)
						break;
					//					for (Planet neutralPlanet : NewState2.NeutralPlanets())
					//					{
					//						NewState2 stateToAdd = NewState2.clone();
					//						stateToAdd.setParent(NewState2);
					//						// Voer actie uit myPlanet valt neutralPlanet aan
					//						stateToAdd.SendFleet(myPlanet, neutralPlanet);
					//						
					//						nextFloor.add(stateToAdd);
					//						int heuristic = stateToAdd.getScore();
					//						if (heuristic == Integer.MAX_VALUE)
					//						{
					//							// Eindstaat gevonden, stoppen met zoeken
					//							endStateFound = true;
					//							break;
					//						}
					//						else if (heuristic > bestHeuristic)
					//						{
					//							bestHeuristic = heuristic;
					//							bestState = stateToAdd;
					//						}
					//					}
					//					
					//					if (endStateFound)
					//						break;
					//					
					//					for (Planet enemyPlanet : NewState2.EnemyPlanets())
					//					{
					//						NewState2 stateToAdd = NewState2.clone();
					//						stateToAdd.setParent(NewState2);
					//						// Voer actie uit myPlanet valt neutralPlanet aan
					//						stateToAdd.SendFleet(myPlanet, enemyPlanet);
					//						
					//						nextFloor.add(stateToAdd);
					//						int heuristic = stateToAdd.getScore();
					//						if (heuristic > bestHeuristic)
					//						{
					//							bestHeuristic = heuristic;
					//							bestState = stateToAdd;
					//						}
					//					}
					//					if (endStateFound)
					//						break;
				}
				if (endStateFound)
					break;
			}
			stateTree.add(nextFloor);
			if (endStateFound)
				break;
		}

		while (bestState.getParent() != state)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;


		//create a source planet, if you want to know what this object does, then read Planet.java

		//create a destination plane

		//(1) implement an algorithm to determine the source planet to send your ships from
		//... code here

		//(2) implement an algorithm to deterimen the destination planet to send your ships to
		//... code here

		//(3) Attack
		if (source != null && dest != null) {
			state.IssueOrder(source, dest);
		}
	}

	static void DepthFirst(NewState2 initialState){
		int searchDepth = 1;
		
		NewState2 bestState = visitState(initialState, searchDepth);
		
		while (bestState.getParent() != initialState)
		{
			bestState = bestState.getParent();
		}

		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		if (source != null && dest != null) {
			initialState.IssueOrder(source, dest);
		}
	}
	
	static NewState2 visitState(NewState2 NewState2, int searchDepth)
	{
		NewState2 result = NewState2;
		
		if (searchDepth == 0)
			return result;
		
		int bestHeuristic = Heuristics2.scoring1(NewState2);
		boolean winStateFound = false;		
		
		// Returns best state found
		for (Planet myPlanet : NewState2.MyPlanets())
		{
			for (Planet notMyPlanet : NewState2.NotMyPlanets())
			{
				NewState2 stateToAdd = NewState2.clone();
				stateToAdd.setParent(NewState2);
				// Voer actie uit; myPlanet valt notMyPlanet aan
				stateToAdd.SendFleet(myPlanet, notMyPlanet);
				
				NewState2 bestResult = visitState(stateToAdd, searchDepth - 1);
				
				int heuristic = Heuristics2.scoring1(bestResult);
				
				if (heuristic == Integer.MAX_VALUE )
				{
					result = bestResult;
					bestHeuristic = heuristic;
					winStateFound = true;
					break;
				}
				else if (heuristic > bestHeuristic)
				{
					result = bestResult;
					bestHeuristic = heuristic;
				}
			}
			if(winStateFound)
				break;
		}
			
		return result;
	}
	
	static double MinMaxFunction(NewState2 state, int depth, NewState2 winningState, final int initialDepth){
		if(depth <= 0){
			return Heuristics2.normalizedScore(state);
		}
		double alpha = Double.NEGATIVE_INFINITY;
		for(NewState2 child : state.getChildren()){
			double nalpha = Math.max(alpha, -MinMaxFunction(child, depth-1, winningState, initialDepth));
			if(initialDepth == depth && nalpha != alpha ) winningState = child;
			alpha = nalpha;
		}
		return alpha;
	}

	public static void MinMax(NewState2 pw, int i) {
		NewState2 winningState = pw.clone();
		MinMaxFunction(pw, i, winningState, i);
		pw.IssueOrder(winningState.preActionSource, winningState.preActionDest);
	}
	
	static void MinMax2(NewState2 pw, int heuristicNumber)
	{
		int searchDepth = 3;
		
		Heuristics2.InitialState = pw;
		NewState2 bestState = MinMax2Recursion(pw, true, Integer.MAX_VALUE, searchDepth, heuristicNumber);
		
		//als er geen betere staat is, doe noodtactiek
		if(bestState == pw){
			Planet largestOwnPlanet = pw.MyPlanets().get(0);
			int largestOwnPlanetFleet = Integer.MIN_VALUE;
			for(Planet own : pw.MyPlanets()){
				if(own.NumShips() > largestOwnPlanetFleet){
					largestOwnPlanet = own;
					largestOwnPlanetFleet = own.NumShips();
				}
			}
			
			Planet smallestNeutralPlanet = null;
			int smallestNeutralPlanetFleet = Integer.MAX_VALUE;
			if(pw.NeutralPlanets().size() > 0){
				smallestNeutralPlanet = pw.NeutralPlanets().get(0);
				smallestNeutralPlanetFleet = pw.NeutralPlanets().get(0).NumShips();
				for(Planet own : pw.NeutralPlanets()){
					if(own.NumShips() < smallestNeutralPlanetFleet){
						smallestNeutralPlanet = own;
						smallestNeutralPlanetFleet = own.NumShips();
					}
				}
			}

			
			Planet smallestEnemyPlanet = pw.EnemyPlanets().get(0);
			int smallestEnemyPlanetFleet = Integer.MAX_VALUE;
			for(Planet own : pw.EnemyPlanets()){
				if(own.NumShips() < smallestEnemyPlanetFleet){
					smallestEnemyPlanet = own;
					smallestEnemyPlanetFleet = own.NumShips();
				}
			}
			
			
			if(pw.NeutralPlanets().size()>0 && smallestNeutralPlanetFleet < smallestEnemyPlanetFleet && largestOwnPlanetFleet/2 > smallestNeutralPlanetFleet + 1){
				bestState.preActionDest = smallestNeutralPlanet;
				bestState.preActionSource = largestOwnPlanet;
			} else {
				bestState.preActionDest = smallestEnemyPlanet;
				bestState.preActionSource = largestOwnPlanet;
			}
		}else{
			while (bestState.getParent() != pw)
			{
				bestState = bestState.getParent();
			}
		}
		
		//einde noodtaktiek
		


		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;

		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		} 
	}
	
	private static NewState2 MinMax2Recursion(NewState2 state, boolean isMyTurn, int greek, int depth, int heuristicNumber)
	{	
		if (depth == 0)
			return state;

		int alpha = Integer.MIN_VALUE;
		int beta = Integer.MAX_VALUE;
		NewState2 bestState = state;
		for (NewState2 childState : state.getChildren(isMyTurn))
		{
			int greekNumber = isMyTurn ? alpha : beta;
			int childStateHeuristic = childState.getScore(heuristicNumber);
			if (childStateHeuristic == Integer.MAX_VALUE && isMyTurn) 
			{
				return childState;
			} 
			else if (childStateHeuristic == Integer.MIN_VALUE && !isMyTurn)
			{
				return childState;
			}
			NewState2 childResultState = MinMax2Recursion(childState, !isMyTurn, greekNumber, depth - 1, heuristicNumber);
			int heuristic = childResultState.getScore(heuristicNumber);
			if (isMyTurn)
			{
				if (heuristic > alpha)
				{
					bestState = childResultState;
					alpha = heuristic;
				}
				if (heuristic >= greek)
				{
					return bestState;
				}
			}
			else
			{
				if (heuristic < beta)
				{
					bestState = childResultState;
					beta = heuristic;
				}
				if (heuristic <= greek)
				{
					return bestState;
				}
			}
		}
		return bestState;
	}
	
}